;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-reader.ss" "lang")((modname u3-huebung) (read-case-sensitive #t) (teachpacks ((lib "image.ss" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "image.ss" "teachpack" "2htdp")))))
;; term defines part of a tree that models arithmetic terms
;; left: number or term - the first operand (which can be a term itself)
;; operator: symbol - the symbole for a mathemical operator
;; right: number or term - the second operand
(define-struct term (left operator right))



;; 6.2
;; contract:    tree-to-infix: term -> (listof any)
;; description: Converts a tree into a onedimensional list of symbols and numbers, that is infix formated.
;; example:     (tree-to-infix (make-term 3 '* 4)) -> (list '< 3 '* 4 '>)

(define (tree-to-infix term)
  (append
   (list '<)
   (cond [(term? (term-left term)) (tree-to-infix (term-left term))]
               [else (list (term-left term))])
   (list (term-operator term))
   (cond [(term? (term-right term)) (tree-to-infix (term-right term))]
               [else (list (term-right term))])
   (list '>)))

;; Tests
(check-expect (tree-to-infix (make-term (make-term 3 '+ 4) '* (make-term 2 '- 1))) (list '< '< 3 '+ 4 '> '* '< 2 '- 1 '> '>))
(check-expect (tree-to-infix (make-term 3 '- (make-term 2 '/ 1))) (list '< 3 '- '< 2 '/ 1 '> '>))



;; 6.3
;; contract:    tree-to-prefix: term -> (listof any)
;; description: Converts a tree into a onedimensional list of symbols and numbers in prefix format.
;; example:     (tree-to-prefix (make-term 6 '/ 3)) -> (list '< '/ 6 3 '>)

(define (tree-to-prefix term)
  (append
   (list '<)
   (list (term-operator term))
   (cond [(term? (term-left term)) (tree-to-prefix (term-left term))]
               [else (list (term-left term))])
   (cond [(term? (term-right term)) (tree-to-prefix (term-right term))]
               [else (list (term-right term))])
   (list '>)))

;; Tests
(check-expect (tree-to-prefix (make-term (make-term 1 '* 8) '* (make-term 5 '- 1))) (list '< '* '< '* 1 8 '> '<'- 5 1 '> '>))
(check-expect (tree-to-prefix (make-term 2 '+ (make-term 5 '/ 1))) (list '< '+ 2 '< '/ 5 1 '> '>))



;; 6.4
;; contract:    tree-to-polish: term -> (listof any)
;; description: Converts a tree into a onedimensional list of symbols and numbers in Polish notation.
;; example:     (tree-to-polish (make-term 3 '* 4)) -> (list '* 3 4)

(define (tree-to-polish term)
  (filter no-bracket (tree-to-prefix term)))

;; Tests
(check-expect (tree-to-polish (make-term (make-term 2 '* 4) '+ (make-term 5 '- 4))) (list '+ '* 2 4 '- 5 4))
(check-expect (tree-to-polish (make-term 5 '/ (make-term 2 '/ 1))) (list '/ 5 '/ 2 1))


;; auxiliary function
;; contract:    no-bracket: any -> boolean
;; description: Gives back false if input is a '< or '>. Otherwise it returns true.
;; example:     (no-bracket '<) -> false

(define (no-bracket term-element)
  (cond [(symbol? term-element) (cond [(or (symbol=? '< term-element) (symbol=? '> term-element)) false]
                                      [else true])]
        [else true]))

;; Tests
(check-expect (no-bracket '>) false)
(check-expect (no-bracket 5) true)



;; 6.5
;; contract:    tree-to-rpn: term -> (listof any)
;; description: Converts a tree into a onedimensional list of symbols and numbers in RPN format.
;; example:     (tree-to-rpn (make-term (make-term 5 '/ 2.5) '+ (make-term 7 '- 3))) -> (list 5 2.5 '/ 7 3 '- '+)

(define (tree-to-rpn term)
    (filter no-bracket (append
                        (list '<)
                        (cond [(term? (term-left term)) (tree-to-rpn (term-left term))]
                              [else (list (term-left term))])
                        (cond [(term? (term-right term)) (tree-to-rpn (term-right term))]
                              [else (list (term-right term))])
                        (list (term-operator term))
                        (list '>))))

;; Tests
(check-expect (tree-to-rpn (make-term (make-term 3 '+ 4) '* (make-term 2 '- 1))) (list 3 4 '+ 2 1 '- '*))
(check-expect (tree-to-rpn (make-term 9 '+ (make-term 8 '/ 2))) (list 9 8 2 '/ '+))



;; 6.6
;; contract:    eval-rpn: (listof any) -> number
;; description: Evaluates a rpn formated list.
;; example:     (eval-rpn (list 3 2 1 '/ '-)) -> 1

;; dont work recursive, just with an atomic term. =(

(define (eval-rpn term)
  (cond [(symbol? (third term))
         (cond [(symbol=? '+ (third term)) (+ (first term) (second term))]
               [(symbol=? '- (third term)) (- (first term) (second term))]
               [(symbol=? '* (third term)) (* (first term) (second term))]
               [(symbol=? '/ (third term)) (/ (first term) (second term))]
               [else 'error])]
         [(number? (third term)) (eval-rpn (rest term))]
         [else empty]))


;; Tests
(check-expect (eval-rpn (list 8 4 '/)) 2)
(check-expect (eval-rpn (list 5 8 4 '/ '+)) 7)



;; This was the idea of a list with the elements prior the first term, the result form the term and the elements after that.
;; This should work recursive but unfortunately dont do so...

;(define (eval-rpn term)
;  (cond [(symbol? (third term))
;         (list (cond [(symbol=? '+ (third term)) (+ (first term) (second term))]
;               [(symbol=? '- (third term)) (- (first term) (second term))]
;               [(symbol=? '* (third term)) (* (first term) (second term))]
;               [(symbol=? '/ (third term)) (/ (first term) (second term))]
;               [else 'error]))
;         ]
;         [(number? (third term)) (cons (first term) (eval-rpn (rest term)))]
;         [else empty]))